{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Delete Duplicate Folders in System"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #array #hash-table #string #hash-function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #数组 #哈希表 #字符串 #哈希函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: deleteDuplicateFolder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除系统中的重复文件夹"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>由于一个漏洞，文件系统中存在许多重复文件夹。给你一个二维数组 <code>paths</code>，其中 <code>paths[i]</code> 是一个表示文件系统中第 <code>i</code> 个文件夹的绝对路径的数组。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>[\"one\", \"two\", \"three\"]</code> 表示路径 <code>\"/one/two/three\"</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果两个文件夹（不需要在同一层级）包含 <strong>非空且</strong><b>相同的&nbsp;</b>子文件夹&nbsp;<strong>集合</strong> 并具有相同的子文件夹结构，则认为这两个文件夹是相同文件夹。相同文件夹的根层级 <strong>不</strong> 需要相同。如果存在两个（或两个以上）<strong>相同</strong> 文件夹，则需要将这些文件夹和所有它们的子文件夹 <strong>标记</strong> 为待删除。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，下面文件结构中的文件夹 <code>\"/a\"</code> 和 <code>\"/b\"</code> 相同。它们（以及它们的子文件夹）应该被 <strong>全部</strong> 标记为待删除：\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li><code>/a</code></li>\n",
    "\t\t<li><code>/a/x</code></li>\n",
    "\t\t<li><code>/a/x/y</code></li>\n",
    "\t\t<li><code>/a/z</code></li>\n",
    "\t\t<li><code>/b</code></li>\n",
    "\t\t<li><code>/b/x</code></li>\n",
    "\t\t<li><code>/b/x/y</code></li>\n",
    "\t\t<li><code>/b/z</code></li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>然而，如果文件结构中还包含路径 <code>\"/b/w\"</code> ，那么文件夹 <code>\"/a\"</code> 和 <code>\"/b\"</code> 就不相同。注意，即便添加了新的文件夹 <code>\"/b/w\"</code> ，仍然认为 <code>\"/a/x\"</code> 和 <code>\"/b/x\"</code> 相同。</li>\n",
    "</ul>\n",
    "\n",
    "<p>一旦所有的相同文件夹和它们的子文件夹都被标记为待删除，文件系统将会 <strong>删除</strong> 所有上述文件夹。文件系统只会执行一次删除操作。执行完这一次删除操作后，不会删除新出现的相同文件夹。</p>\n",
    "\n",
    "<p>返回二维数组<em> </em><code>ans</code> ，该数组包含删除所有标记文件夹之后剩余文件夹的路径。路径可以按 <strong>任意顺序</strong> 返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/19/lc-dupfolder1.jpg\" style=\"width: 200px; height: 218px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>paths = [[\"a\"],[\"c\"],[\"d\"],[\"a\",\"b\"],[\"c\",\"b\"],[\"d\",\"a\"]]\n",
    "<strong>输出：</strong>[[\"d\"],[\"d\",\"a\"]]\n",
    "<strong>解释：</strong>文件结构如上所示。\n",
    "文件夹 \"/a\" 和 \"/c\"（以及它们的子文件夹）都会被标记为待删除，因为它们都包含名为 \"b\" 的空文件夹。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/19/lc-dupfolder2.jpg\" style=\"width: 200px; height: 355px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>paths = [[\"a\"],[\"c\"],[\"a\",\"b\"],[\"c\",\"b\"],[\"a\",\"b\",\"x\"],[\"a\",\"b\",\"x\",\"y\"],[\"w\"],[\"w\",\"y\"]]\n",
    "<strong>输出：</strong>[[\"c\"],[\"c\",\"b\"],[\"a\"],[\"a\",\"b\"]]\n",
    "<strong>解释：</strong>文件结构如上所示。\n",
    "文件夹 \"/a/b/x\" 和 \"/w\"（以及它们的子文件夹）都会被标记为待删除，因为它们都包含名为 \"y\" 的空文件夹。\n",
    "注意，文件夹 \"/a\" 和 \"/c\" 在删除后变为相同文件夹，但这两个文件夹不会被删除，因为删除只会进行一次，且它们没有在删除前被标记。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/19/lc-dupfolder3.jpg\" style=\"width: 200px; height: 201px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>paths = [[\"a\",\"b\"],[\"c\",\"d\"],[\"c\"],[\"a\"]]\n",
    "<strong>输出：</strong>[[\"c\"],[\"c\",\"d\"],[\"a\"],[\"a\",\"b\"]]\n",
    "<strong>解释：</strong>文件系统中所有文件夹互不相同。\n",
    "注意，返回的数组可以按不同顺序返回文件夹路径，因为题目对顺序没有要求。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/19/lc-dupfolder4_.jpg\" style=\"width: 300px; height: 290px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>paths = [[\"a\"],[\"a\",\"x\"],[\"a\",\"x\",\"y\"],[\"a\",\"z\"],[\"b\"],[\"b\",\"x\"],[\"b\",\"x\",\"y\"],[\"b\",\"z\"]]\n",
    "<strong>输出：</strong>[]\n",
    "<strong>解释：</strong>文件结构如上所示。\n",
    "文件夹 \"/a/x\" 和 \"/b/x\"（以及它们的子文件夹）都会被标记为待删除，因为它们都包含名为 \"y\" 的空文件夹。\n",
    "文件夹 \"/a\" 和 \"/b\"（以及它们的子文件夹）都会被标记为待删除，因为它们都包含一个名为 \"z\" 的空文件夹以及上面提到的文件夹 \"x\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/19/lc-dupfolder5_.jpg\" style=\"width: 300px; height: 282px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>paths = [[\"a\"],[\"a\",\"x\"],[\"a\",\"x\",\"y\"],[\"a\",\"z\"],[\"b\"],[\"b\",\"x\"],[\"b\",\"x\",\"y\"],[\"b\",\"z\"],[\"b\",\"w\"]]\n",
    "<strong>输出：</strong>[[\"b\"],[\"b\",\"w\"],[\"b\",\"z\"],[\"a\"],[\"a\",\"z\"]]\n",
    "<strong>解释：</strong>本例与上例的结构基本相同，除了新增 \"/b/w\" 文件夹。\n",
    "文件夹 \"/a/x\" 和 \"/b/x\" 仍然会被标记，但 \"/a\" 和 \"/b\" 不再被标记，因为 \"/b\" 中有名为 \"w\" 的空文件夹而 \"/a\" 没有。\n",
    "注意，\"/a/z\" 和 \"/b/z\" 不会被标记，因为相同子文件夹的集合必须是非空集合，但这两个文件夹都是空的。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= paths.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= paths[i].length &lt;= 500</code></li>\n",
    "\t<li><code>1 &lt;= paths[i][j].length &lt;= 10</code></li>\n",
    "\t<li><code>1 &lt;= sum(paths[i][j].length) &lt;= 2 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>path[i][j]</code> 由小写英文字母组成</li>\n",
    "\t<li>不会存在两个路径都指向同一个文件夹的情况</li>\n",
    "\t<li>对于不在根层级的任意文件夹，其父文件夹也会包含在输入中</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [delete-duplicate-folders-in-system](https://leetcode.cn/problems/delete-duplicate-folders-in-system/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [delete-duplicate-folders-in-system](https://leetcode.cn/problems/delete-duplicate-folders-in-system/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"a\"],[\"c\"],[\"d\"],[\"a\",\"b\"],[\"c\",\"b\"],[\"d\",\"a\"]]', '[[\"a\"],[\"c\"],[\"a\",\"b\"],[\"c\",\"b\"],[\"a\",\"b\",\"x\"],[\"a\",\"b\",\"x\",\"y\"],[\"w\"],[\"w\",\"y\"]]', '[[\"a\",\"b\"],[\"c\",\"d\"],[\"c\"],[\"a\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\r\n",
    "    def __init__(self) -> None:\r\n",
    "        self.hsh = \"\"\r\n",
    "        self.children: dict[str, TreeNode] = dict()\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\r\n",
    "        root = TreeNode()\r\n",
    "        # construct the tree\r\n",
    "        for pth in paths:\r\n",
    "            node = root\r\n",
    "            for val in pth:\r\n",
    "                if val not in node.children:\r\n",
    "                    node.children[val] = TreeNode()\r\n",
    "                node = node.children[val]\r\n",
    "        \r\n",
    "        cnt: dict[str, int] = dict()\r\n",
    "        # postorder traversal to get hash of subtree\r\n",
    "        def postorder(node: TreeNode) -> None:\r\n",
    "            if not node.children: return\r\n",
    "\r\n",
    "            for hsh in sorted(node.children.keys()):\r\n",
    "                postorder(node.children[hsh])\r\n",
    "                node.hsh += \"(\" + hsh + node.children[hsh].hsh + \")\"\r\n",
    "\r\n",
    "            if node.hsh not in cnt: cnt[node.hsh] = 0\r\n",
    "            cnt[node.hsh] += 1\r\n",
    "        # preorder traversal to avoid duplicates, and generate answer\r\n",
    "        def preorder(node: TreeNode) -> None:\r\n",
    "            for hsh, child in node.children.items():\r\n",
    "                if child.hsh == \"\" or cnt[child.hsh] == 1:\r\n",
    "                    cur.append(hsh)\r\n",
    "                    res.append(cur.copy())\r\n",
    "                    preorder(child)\r\n",
    "                    cur.pop()\r\n",
    "        \r\n",
    "        postorder(root)\r\n",
    "        res: list[list[str]] = list()\r\n",
    "        cur: list[str] = list()\r\n",
    "        preorder(root)\r\n",
    "\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.dct = dict()\n",
    "        self.serial = \"there_is_a_bug\"\n",
    "        self.count = defaultdict(int)\n",
    "        self.ans = []\n",
    "        return\n",
    "\n",
    "    def update(self, word):\n",
    "        cur = self.dct\n",
    "        for w in word:\n",
    "            if w not in cur:\n",
    "                cur[w] = dict()\n",
    "            cur = cur[w]\n",
    "        return\n",
    "\n",
    "    def add_serial(self, cur):\n",
    "        # 到达叶子节点直接返回空元组\n",
    "        if not cur:\n",
    "            return ()\n",
    "        # 依次将子节点的文件名和子节点的子文件夹序列以元组形式拼接添加到列表\n",
    "        res = []\n",
    "        for w in cur:\n",
    "            serial = (w, self.add_serial(cur[w]))\n",
    "            res.append(serial)\n",
    "        # 排序后转成可作为哈希键的元组同时对序列进行计数\n",
    "        res.sort()\n",
    "        cur[self.serial] = tuple(res)\n",
    "        self.count[cur[self.serial]] += 1\n",
    "        return cur[self.serial]\n",
    "\n",
    "    def get_drop_duplicates_paths(self, pre, cur):\n",
    "        # 如果子文件序列的计数不唯一则停止搜索\n",
    "        if self.serial in cur and self.count[cur[self.serial]] > 1:\n",
    "            return\n",
    "        # 将截至目前的非重复文件路径加到最终结果\n",
    "        if pre:\n",
    "            self.ans.append(pre)\n",
    "        # 遍历子文件夹\n",
    "        for w in cur:\n",
    "            if w != self.serial:\n",
    "                self.get_drop_duplicates_paths(pre+[w], cur[w])\n",
    "        return\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicateFolder(self, paths):\n",
    "        # 构建字典树\n",
    "        trie = Trie()\n",
    "        for path in paths:\n",
    "            trie.update(path)\n",
    "        # 添加序列化的子文件夹\n",
    "        trie.add_serial(trie.dct)\n",
    "        # 获取非重复文件夹的路径\n",
    "        trie.get_drop_duplicates_paths([], trie.dct)\n",
    "        return trie.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.dct = dict()\n",
    "        self.serial = \"there_is_a_bug\"\n",
    "        self.count = defaultdict(int)\n",
    "        self.ans = []\n",
    "        return\n",
    "\n",
    "    def update(self, word):\n",
    "        cur = self.dct\n",
    "        for w in word:\n",
    "            if w not in cur:\n",
    "                cur[w] = dict()\n",
    "            cur = cur[w]\n",
    "        return\n",
    "\n",
    "    def add_serial(self, cur):\n",
    "        # 到达叶子节点直接返回空元组\n",
    "        if not cur:\n",
    "            return ()\n",
    "        # 依次将子节点的文件名和子节点的子文件夹序列以元组形式拼接添加到列表\n",
    "        res = []\n",
    "        for w in cur:\n",
    "            serial = (w, self.add_serial(cur[w]))\n",
    "            res.append(serial)\n",
    "        # 排序后转成可作为哈希键的元组同时对序列进行计数\n",
    "        res.sort()\n",
    "        cur[self.serial] = tuple(res)\n",
    "        self.count[cur[self.serial]] += 1\n",
    "        return cur[self.serial]\n",
    "\n",
    "    def get_drop_duplicates_paths(self, pre, cur):\n",
    "        # 如果子文件序列的计数不唯一则停止搜索\n",
    "        if self.serial in cur and self.count[cur[self.serial]] > 1:\n",
    "            return\n",
    "        # 将截至目前的非重复文件路径加到最终结果\n",
    "        if pre:\n",
    "            self.ans.append(pre)\n",
    "        # 遍历子文件夹\n",
    "        for w in cur:\n",
    "            if w != self.serial:\n",
    "                self.get_drop_duplicates_paths(pre+[w], cur[w])\n",
    "        return\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicateFolder(self, paths):\n",
    "        # 构建字典树\n",
    "        trie = Trie()\n",
    "        for path in paths:\n",
    "            trie.update(path)\n",
    "        # 添加序列化的子文件夹\n",
    "        trie.add_serial(trie.dct)\n",
    "        # 获取非重复文件夹的路径\n",
    "        trie.get_drop_duplicates_paths([], trie.dct)\n",
    "        return trie.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.strs = ''\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n",
    "        root = TrieNode()\n",
    "        for p in paths:\n",
    "            node = root \n",
    "            for c in p:\n",
    "                if c not in node.children:\n",
    "                    node.children[c] = TrieNode()\n",
    "                node = node.children[c]\n",
    "\n",
    "        counter = collections.Counter()\n",
    "        def dfs(node):\n",
    "            if not node.children:\n",
    "                return ''\n",
    "            path = []\n",
    "            for c in node.children:\n",
    "                path.append(c + '[' + dfs(node.children[c]) + ']')\n",
    "            path.sort()\n",
    "            node.strs = ''.join(path)\n",
    "            counter[''.join(path)] += 1 \n",
    "            return node.strs \n",
    "        dfs(root)\n",
    "        res = []\n",
    "        def helper(root, path):\n",
    "            if counter[root.strs] > 1:\n",
    "                return \n",
    "            if path:\n",
    "                res.append(path[:])\n",
    "            for c in root.children:\n",
    "                helper(root.children[c], path + [c])\n",
    "        \n",
    "        helper(root, [])\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.strs = ''\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n",
    "        root = TrieNode()\n",
    "        for p in paths:\n",
    "            node = root \n",
    "            for c in p:\n",
    "                if c not in node.children:\n",
    "                    node.children[c] = TrieNode()\n",
    "                node = node.children[c]\n",
    "\n",
    "        counter = collections.Counter()\n",
    "        def dfs(node):\n",
    "            if not node.children:\n",
    "                return ''\n",
    "            path = []\n",
    "            for c in node.children:\n",
    "                path.append(c + '[' + dfs(node.children[c]) + ']')\n",
    "            path.sort()\n",
    "            node.strs = ''.join(path)\n",
    "            counter[''.join(path)] += 1 \n",
    "            return node.strs \n",
    "        dfs(root)\n",
    "        res = []\n",
    "        def helper(root, path):\n",
    "            if counter[root.strs] > 1:\n",
    "                return \n",
    "            if path:\n",
    "                res.append(path[:])\n",
    "            for c in root.children:\n",
    "                helper(root.children[c], path + [c])\n",
    "        \n",
    "        helper(root, [])\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.dct = dict()\n",
    "        return\n",
    "\n",
    "    def update(self, word):\n",
    "        cur = self.dct\n",
    "        for w in word:\n",
    "            if w not in cur:\n",
    "                cur[w] = dict()\n",
    "            cur = cur[w]\n",
    "        cur[\"There_is_End\"] = 1\n",
    "        return\n",
    "\n",
    "\n",
    "# def dfs(cur):\n",
    "#     nonlocal idx\n",
    "#     son = []\n",
    "#     for key in sorted(cur.keys()):\n",
    "#         if key != \"There_is_End\":\n",
    "#             son.append((key, dfs(cur[key])))\n",
    "#     if not son:\n",
    "#         return 0\n",
    "#     state = tuple(son)\n",
    "#     if state in seen:\n",
    "#         idy = seen[state]\n",
    "#         repeat.add(idy)\n",
    "#         cur[\"There_is_sub\"] = idy\n",
    "#         return idy\n",
    "#     idx += 1\n",
    "#     seen[state] = idx\n",
    "#     return idx\n",
    "\n",
    "# idx = 0\n",
    "# repeat = set()\n",
    "# seen = dict()\n",
    "# dfs(root)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n",
    "        trie = Trie()\n",
    "        for path in paths:\n",
    "            trie.update([\"/\"] + path)\n",
    "\n",
    "#         def dfs(cur):\n",
    "#             son = []\n",
    "#             for key in sorted(cur.keys()):\n",
    "#                 if key != \"There_is_End\":\n",
    "#                     son.append((key, dfs(cur[key])))\n",
    "#             sub = tuple(son)\n",
    "#             cur[\"There_is_sub\"] = sub\n",
    "#             count[sub] += 1\n",
    "#             return sub\n",
    "\n",
    "#         count = defaultdict(int)\n",
    "#         dfs(trie.dct)\n",
    "#         count[()] = 1\n",
    "\n",
    "        def dfs(cur):\n",
    "            nonlocal idx\n",
    "            son = []\n",
    "            for key in sorted(cur.keys()):\n",
    "                if key != \"There_is_End\":\n",
    "                    son.append((key, dfs(cur[key])))\n",
    "            if not son:\n",
    "                cur[\"There_is_sub\"] = 0\n",
    "                return 0\n",
    "            state = tuple(son)\n",
    "            if state in seen:\n",
    "                idy = seen[state]\n",
    "                repeat.add(idy)\n",
    "                cur[\"There_is_sub\"] = idy\n",
    "                return idy\n",
    "            idx += 1\n",
    "            seen[state] = idx\n",
    "            cur[\"There_is_sub\"] = idx\n",
    "            return idx\n",
    "\n",
    "        idx = 0\n",
    "        repeat = set()\n",
    "        seen = dict()\n",
    "        dfs(trie.dct)\n",
    "        if 0 in repeat:\n",
    "            repeat.discard(0)\n",
    "\n",
    "        ans = []\n",
    "        def dfs(pre, cur):\n",
    "            if cur[\"There_is_sub\"] not in repeat:\n",
    "                if len(pre) > 1:\n",
    "                    ans.append(pre[1:])\n",
    "            else:\n",
    "                return\n",
    "            for nex in cur:\n",
    "                if nex != \"There_is_End\" and nex != \"There_is_sub\":\n",
    "                    dfs(pre+[nex], cur[nex])\n",
    "            return\n",
    "        dfs([], trie.dct)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n",
    "\n",
    "        dct = dict()\n",
    "        for path in paths:\n",
    "            cur = dct\n",
    "            for w in path:\n",
    "                if w not in cur:\n",
    "                    cur[w] = dict()\n",
    "                cur = cur[w]\n",
    "            cur[\"**\"] = 1\n",
    "\n",
    "        def dfs(node, cur_w):\n",
    "            if not node:\n",
    "                return (0,)\n",
    "\n",
    "            state = tuple()\n",
    "            for ww in sorted(node):\n",
    "                if ww != \"**\" and ww != \"##\":\n",
    "                    state += dfs(node[ww], ww)\n",
    "            if state not in seen:\n",
    "                seen[state] = len(seen) + 1\n",
    "            node[\"##\"] = seen[state]\n",
    "            cnt[seen[state]] += 1\n",
    "            return (seen[state], cur_w)\n",
    "\n",
    "        seen = dict()\n",
    "        cnt = Counter()\n",
    "        dfs(dct, \"\")\n",
    "\n",
    "        ans = []\n",
    "        for path in paths:\n",
    "            node_ = dct\n",
    "            for p in path:\n",
    "                node_ = node_[p]\n",
    "                if cnt[node_[\"##\"]] > 1 and node_[\"##\"] > 1:\n",
    "                    break\n",
    "            else:\n",
    "                ans.append(path[:])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n",
    "        trie = {}\n",
    "\n",
    "        for pt in paths:\n",
    "            p = trie\n",
    "            for x in pt:\n",
    "                if x not in p:\n",
    "                    p[x] = {}\n",
    "                p = p[x]\n",
    "\n",
    "        def serial(x):\n",
    "            if 'serial' in x:\n",
    "                return x['serial']\n",
    "\n",
    "            root = []\n",
    "            ret = []\n",
    "\n",
    "            for k in sorted(list(x.keys())):\n",
    "                if k == 'serial':\n",
    "                    continue\n",
    "\n",
    "                root.append(k)\n",
    "                sk = serial(x[k])\n",
    "\n",
    "                if sk:\n",
    "                    ret.append(k + '(' + sk + ')')\n",
    "\n",
    "            ret.append(','.join(root))\n",
    "            \n",
    "            ret = ','.join(ret)\n",
    "\n",
    "            x['serial'] = ret\n",
    "\n",
    "            return ret\n",
    "\n",
    "        cnts = defaultdict(int)\n",
    "\n",
    "        def dfs(x):\n",
    "            s = serial(x)\n",
    "            if s != '':\n",
    "                cnts[s] += 1\n",
    "\n",
    "            for k in x:\n",
    "                if k == 'serial':\n",
    "                    continue\n",
    "                dfs(x[k])\n",
    "\n",
    "        dfs(trie)\n",
    "\n",
    "        ret = []\n",
    "        path = []\n",
    "\n",
    "        def bt(x):\n",
    "            s = serial(x)\n",
    "\n",
    "            if cnts[s] > 1:\n",
    "                return\n",
    "                \n",
    "            if path:\n",
    "                ret.append(list(path))\n",
    "\n",
    "            for k in x:\n",
    "                if k == 'serial':\n",
    "                    continue\n",
    "\n",
    "                path.append(k)\n",
    "                bt(x[k])\n",
    "                path.pop()\n",
    "\n",
    "        bt(trie)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n",
    "        dc, dcc, res = {}, defaultdict(int), []\n",
    "        for lis in paths:\n",
    "            node = dc\n",
    "            for i in lis:\n",
    "                if i not in node: node[i] = {}\n",
    "                node = node[i]\n",
    "        def getN(node):\n",
    "            if not node: return \"\"\n",
    "            lis = []\n",
    "            for i in sorted(node): lis.append(f\"{i}({getN(node[i])})\")\n",
    "            lis = \",\".join(lis)\n",
    "            node[\"#\"], dcc[lis] = lis, dcc[lis] + 1\n",
    "            return lis\n",
    "        getN(dc)\n",
    "        def dfs(node, ss):\n",
    "            for i in node:\n",
    "                if i != '#' and (not node[i] or dcc[node[i]['#']] == 1):\n",
    "                    res.append(ss + [i])\n",
    "                    dfs(node[i], ss + [i])\n",
    "        dfs(dc, [])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n",
    "        dc, dcc, res = {}, defaultdict(int), []\n",
    "        for lis in paths:\n",
    "            node = dc\n",
    "            for i in lis:\n",
    "                if i not in node: node[i] = {}\n",
    "                node = node[i]\n",
    "        def getN(node):\n",
    "            if not node: return \"\"\n",
    "            lis = []\n",
    "            for i in sorted(node): lis.append(f\"{i}({getN(node[i])})\")\n",
    "            lis = \",\".join(lis)\n",
    "            node[\"#\"], dcc[lis] = lis, dcc[lis] + 1\n",
    "            return lis\n",
    "        getN(dc)\n",
    "        def dfs(node, ss):\n",
    "            for i in node:\n",
    "                if i != '#' and (not node[i] or dcc[node[i]['#']] == 1):\n",
    "                    res.append(ss + [i])\n",
    "                    dfs(node[i], ss + [i])\n",
    "        dfs(dc, [])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n",
    "        dc, dcc, res = {}, defaultdict(int), []\n",
    "        for lis in paths:\n",
    "            node = dc\n",
    "            for i in lis:\n",
    "                if i not in node: node[i] = {}\n",
    "                node = node[i]\n",
    "        def getN(node):\n",
    "            if not node: return \"\"\n",
    "            lis = []\n",
    "            for i in sorted(node): lis.append(f\"{i}({getN(node[i])})\")\n",
    "            lis = \",\".join(lis)\n",
    "            node[\"#\"], dcc[lis] = lis, dcc[lis] + 1\n",
    "            return lis\n",
    "        getN(dc)\n",
    "        def dfs(node, ss):\n",
    "            for i in node:\n",
    "                if i != '#' and (not node[i] or dcc[node[i]['#']] == 1):\n",
    "                    res.append(ss + [i])\n",
    "                    dfs(node[i], ss + [i])\n",
    "        dfs(dc, [])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n",
    "        class Tree():\n",
    "            def __init__(self, val = 0):\n",
    "                self.children = {}\n",
    "                self.val = val\n",
    "                self.deleted = False\n",
    "        \n",
    "        def dfs(cur, path):\n",
    "            for k,v in cur.children.items():\n",
    "                if not v.deleted:\n",
    "                    dfs(v,path+[k])\n",
    "            if path:\n",
    "                ans.append(path)\n",
    "\n",
    "\n",
    "        def insert(path):\n",
    "            cur = root\n",
    "            for c in path:\n",
    "                if c not in cur.children:\n",
    "                    cur.children[c] = Tree()\n",
    "                cur = cur.children[c]\n",
    "        tree_dict = {}\n",
    "        def serialize(tree):\n",
    "            ans = \"(\"\n",
    "            for k in sorted(tree.children.keys()):\n",
    "                v = tree.children[k]\n",
    "                ans += k + serialize(v)\n",
    "            # for k,v in tree.children.items():\n",
    "            #     ans += k  + serialize(v)\n",
    "            ans+=\")\"\n",
    "            if ans != \"()\":\n",
    "                if ans not in tree_dict:\n",
    "                    tree_dict[ans] = [tree]\n",
    "                else:\n",
    "                    tree_dict[ans].append(tree)\n",
    "            return ans\n",
    "\n",
    "        root = Tree()\n",
    "        for path in paths:\n",
    "            insert(path)\n",
    "        serialize(root)\n",
    "        print(tree_dict)\n",
    "\n",
    "        for nodes in tree_dict.values():\n",
    "            if len(nodes)>1:\n",
    "                for node in nodes:\n",
    "                    node.deleted = True\n",
    "        \n",
    "        ans = []\n",
    "        dfs(root, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.name = ''\n",
    "\n",
    "    def insert(self, words) -> None:\n",
    "        node = self\n",
    "        for w in words:\n",
    "            if w not in node.children:\n",
    "                node.children[w] = Trie()\n",
    "                node.children[w].name = w\n",
    "            node = node.children[w]\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n",
    "        t = Trie()\n",
    "        for path in paths:\n",
    "            t.insert(path)\n",
    "        \n",
    "        cnt = Counter()\n",
    "        dic = {}\n",
    "        def dfs(node):\n",
    "            res = ''\n",
    "            for ch in sorted(node.children):\n",
    "                dfs(node.children[ch])\n",
    "                res += '(' + node.children[ch].name + ')' + '(' + dic[node.children[ch]] + ')'\n",
    "            dic[node] = res\n",
    "            cnt[res] += 1\n",
    "        \n",
    "        dfs(t)\n",
    "        ans = []\n",
    "        def add_path(node, p):\n",
    "            if node.name:\n",
    "                p.append(node.name)\n",
    "                if node.children and cnt[dic[node]] > 1:\n",
    "                    return\n",
    "                ans.append(p[::])\n",
    "            \n",
    "            for ch in node.children:\n",
    "                add_path(node.children[ch], p[::])\n",
    "\n",
    "        add_path(t, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.isEnd = False\n",
    "        self.isDel = False\n",
    "        self.name = ''\n",
    "\n",
    "    def insert(self, words) -> None:\n",
    "        node = self\n",
    "        for w in words:\n",
    "            if w not in node.children:\n",
    "                node.children[w] = Trie()\n",
    "                node.children[w].name = w\n",
    "            node = node.children[w]\n",
    "        node.isEnd = True\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n",
    "        t = Trie()\n",
    "        for path in paths:\n",
    "            t.insert(path)\n",
    "        \n",
    "        cnt = Counter()\n",
    "        dic = {}\n",
    "\n",
    "        def dfs(node):\n",
    "            res = ''\n",
    "            for ch in sorted(node.children):\n",
    "                dfs(node.children[ch])\n",
    "                res += '(' + node.children[ch].name + ')' + '(' + dic[node.children[ch]] + ')'\n",
    "            dic[node] = res\n",
    "            cnt[res] += 1\n",
    "        \n",
    "        dfs(t)\n",
    "\n",
    "        def del_node(node):\n",
    "            res = dic[node]\n",
    "            for ch in sorted(node.children):\n",
    "                del_node(node.children[ch])\n",
    "            \n",
    "            if node.children and cnt[res] > 1:\n",
    "                node.isDel = True\n",
    "        \n",
    "        del_node(t)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        def add_path(node, p):\n",
    "            if node.name:\n",
    "                p.append(node.name)\n",
    "                if node.isDel:\n",
    "                    return\n",
    "                ans.append(p[::])\n",
    "            \n",
    "            for ch in node.children:\n",
    "                add_path(node.children[ch], p[::])\n",
    "\n",
    "        add_path(t, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from time import time\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.orig = None\n",
    "        self.children = {}\n",
    "        self.sorted_keys = None\n",
    "        self.start = None\n",
    "        self.end = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n",
    "        _start = time()\n",
    "        word_map = {}\n",
    "        root = TreeNode(-2)\n",
    "        for p in paths:\n",
    "            curr = root\n",
    "            for i, w in enumerate(p):\n",
    "                pi = word_map.setdefault(w, len(word_map))\n",
    "                if pi in curr.children:\n",
    "                    curr = curr.children[pi]\n",
    "                else:\n",
    "                    n_ = TreeNode(pi)\n",
    "                    curr.children[pi] = n_\n",
    "                    curr = n_\n",
    "            curr.orig = p\n",
    "        #print(\"build tree\", time() - _start)\n",
    "        tree_order = []\n",
    "        node_info = []\n",
    "\n",
    "        def dfs(node):\n",
    "            tree_order.append(node.val)\n",
    "            node_info.append(node)\n",
    "            node.start = len(tree_order)\n",
    "            node.sorted_keys = sorted(node.children.keys())\n",
    "            for k in node.sorted_keys:\n",
    "                dfs(node.children[k])\n",
    "            tree_order.append(-1)\n",
    "            node.end = len(tree_order)\n",
    "            node_info.append(None)\n",
    "\n",
    "        dfs(root)\n",
    "        #print(\"dfs\", time() - _start)\n",
    "        # Build a suffix array\n",
    "        N = len(tree_order)\n",
    "        L = 1\n",
    "        rank = [0] * N\n",
    "        suffix = [(v, i) for i, v in enumerate(tree_order)]\n",
    "        while True:\n",
    "            suffix.sort(key=lambda x: x[0])\n",
    "            r = 0\n",
    "            lk = None\n",
    "            for v, i in suffix:\n",
    "                if v != lk:\n",
    "                    r += 1\n",
    "                    lk = v\n",
    "                rank[i] = r\n",
    "            if L >= N or r == N:\n",
    "                break\n",
    "            for i in range(N):\n",
    "                suffix[i] = ((rank[i], rank[i + L] if i + L < N else 0), i)\n",
    "            L += L\n",
    "        si = [s[1] for s in suffix]\n",
    "        for i in range(N):\n",
    "            rank[i] -= 1\n",
    "        #print(\"suffix\", time() - _start)\n",
    "        height = [0] * N\n",
    "        curr_height = 0\n",
    "        for i in range(N):\n",
    "            if rank[i] == 0:\n",
    "                height[i] = 0\n",
    "                curr_height = 0\n",
    "            else:\n",
    "                prev = si[rank[i] - 1]\n",
    "                while i + curr_height < N and prev + curr_height < N and tree_order[i + curr_height] == tree_order[prev + curr_height]:\n",
    "                    curr_height += 1\n",
    "                height[i] = curr_height\n",
    "                if curr_height > 0:\n",
    "                    curr_height -= 1\n",
    "        #print(\"height\", time() - _start)\n",
    "        #print(word_map)\n",
    "        #print(tree_order)\n",
    "        #print(si)\n",
    "        #print(height)\n",
    "        deleted = set()\n",
    "                    \n",
    "        # Check with prev\n",
    "        last = None\n",
    "        curr_height = 0\n",
    "        for i in si:\n",
    "            if i <= 0 or node_info[i - 1] is None or node_info[i - 1].end - node_info[i - 1].start <= 1:\n",
    "                # Not a valid children range\n",
    "                curr_height = min(curr_height, height[i])\n",
    "            else:\n",
    "                if last is not None:\n",
    "                    # Check deleted\n",
    "                    curr_height = min(curr_height, height[i])\n",
    "                    #print(last, i, curr_height, node_info[i - 1].start, node_info[i - 1].end)\n",
    "                    if curr_height >= node_info[i - 1].end - node_info[i - 1].start:\n",
    "                        deleted.add(last)\n",
    "                        deleted.add(i)\n",
    "                last = i\n",
    "                curr_height = N - i\n",
    "        #print(\"deleted\", time() - _start)\n",
    "        #print(deleted)\n",
    "                \n",
    "        result = []\n",
    "        def dfs2(node):\n",
    "            if node.start in deleted:\n",
    "                return\n",
    "            if node.val >= 0:\n",
    "                result.append(node.orig)\n",
    "            for k in node.sorted_keys:\n",
    "                dfs2(node.children[k])\n",
    "\n",
    "        dfs2(root)\n",
    "        #print(\"dfs2\", time() - _start)\n",
    "        return result\n",
    "\n",
    "\n",
    "# 作者：灵剑2012\n",
    "# 链接：https://leetcode.cn/problems/delete-duplicate-folders-in-system/solutions/895540/hou-zhui-shu-zu-jie-fa-by-ling-jian-2012-ogk1/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(999999)\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.child = SortedDict()\n",
    "        self.s = ''\n",
    "        self.hash_s = ''\n",
    "        self.is_end = False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n",
    "        root = Node()\n",
    "        root.s = ''\n",
    "\n",
    "        # 建树\n",
    "        for p in paths:\n",
    "            cur = root\n",
    "            for ss in p:\n",
    "                if ss not in cur.child:\n",
    "                    t = Node()\n",
    "                    t.s = ss\n",
    "                    cur.child[ss] = t\n",
    "                cur = cur.child[ss]\n",
    "            cur.is_end = True\n",
    "\n",
    "            # 统计每一个子树的后序序列(相当于每一棵子树序列化)\n",
    "        tot_counter = Counter()\n",
    "\n",
    "        def dfs1(cur: Node) -> str:\n",
    "            for ne in cur.child.values():\n",
    "                cur.hash_s += dfs1(ne)\n",
    "\n",
    "            tot_counter[cur.hash_s] += 1\n",
    "            return \"<\" + cur.hash_s + cur.s + \">\"\n",
    "\n",
    "        dfs1(root)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        def dfs2(cur: Node, path: List):\n",
    "            path.append(cur.s)\n",
    "            if cur.is_end:\n",
    "                ans.append(path[1:].copy())\n",
    "\n",
    "            for ne in cur.child.values():\n",
    "                if len(ne.child) and tot_counter[ne.hash_s] >= 2:\n",
    "                    continue\n",
    "\n",
    "                dfs2(ne, path)\n",
    "\n",
    "            path.pop(-1)\n",
    "\n",
    "        dfs2(root, [])\n",
    "\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
